#include <stdio.h>
#include <stdlib.h>

#define MVNum 100
typedef enum{FALSE,TRUE} Boolean;

typedef char VerTexType;
typedef int ArcType;

typedef struct{
  VerTexType vexs[MVNum];
  ArcType arcs[MVNum][MVNum];
  int vexnum, arcnum;
} MGraph;

void create_graph(MGraph ** G_pp, char * graph_data_filename)
{
    FILE * fp;
    size_t len = 0;
    ssize_t read;

    int num_nodes, num_edges;
    *G_pp = (MGraph *)malloc(sizeof(MGraph));
    MGraph *g_pp = *G_pp;
    fp = fopen(graph_data_filename, "r");
    if (fp == NULL)
       printf("Read Error\n");//    exit(EXIT_FAILURE);
    fscanf(fp, "%d %d\n", &num_nodes, &num_edges);
    printf("Number of vertices:%d \n Number of sides： %d\n",num_nodes,num_edges);
    g_pp->vexnum=num_nodes;
    g_pp->arcnum=num_edges;

    char cx,cy;
    int x,y;
    for (int i = 0; i < num_nodes; ++i) {
        fscanf(fp, "%c ",&g_pp->vexs[i]);
        printf("%c ",g_pp->vexs[i]);
    }
    printf("\n");
    fscanf(fp, "\n",&g_pp->vexs[num_nodes]);
    for (int i = 0; i < num_edges; ++i) {
        for (int j = 0; j < num_edges; ++j) {
            g_pp->arcs[i][j]=0;
        }
    }
        //写入矩阵
    printf("------All sides------\n");
    for (int i = 0; i < num_edges; ++i) {
        fscanf(fp, "%c %c\n",&cx,&cy);
        printf("%c %c ",cx,cy);
        x=(int)cx-97;
        y=(int)cy-97;
        g_pp->arcs[x][y]=1;
        printf("\n");
    }
    printf("\n");
    printf("   -----print matrix-----\n");
    for (int i = 0; i < num_edges; ++i) {
        for (int j = 0; j < num_edges; ++j) {
            printf("%d  ",g_pp->arcs[i][j]);
        }
        printf("\n");
    }
    fclose(fp);
}

void dfs(MGraph *G, int i, Boolean visited[], char * result_sequence, int * visited_order)
{
    int j;
    result_sequence[*visited_order]=G->vexs[i];
    *visited_order=*visited_order+1;
    visited[i]=TRUE;
    for(j=0;j<G->vexnum;j++){
        if(G->arcs[i][j]==1 && ! visited[j]){
            dfs(G,j,visited,result_sequence,visited_order);
        }
    }
}

int locate_vertex(MGraph * G, char vertex_name) {
    for (int i = 0; i < G->vexnum; i++) {
        if (G->vexs[i]==vertex_name){
            return i;
        }
    }
    return -1;
}
void bfs(MGraph *G, int k, Boolean visited[], char * visited_sequence)
{
    int j,i,l=0,m=0;
    char t[MVNum];
    for(i=0; i<MVNum; i++) {
        visited[i] = FALSE;
        visited_sequence[i]=0;
        t[i]=NULL;
    }
    visited_sequence[m]=G->vexs[k];
    t[m]=G->vexs[k];
    l=locate_vertex(G,t[m]);
    visited[l] = TRUE;
    m++;
    for (int g=0; g < G->vexnum;g++) {
        l=locate_vertex(G,t[g]);
        if(locate_vertex(G,t[g])==-1){
            printf("\n");
            return;
        }
        printf("%d,",g);
        for(j=0;j<G->vexnum;j++){
            if(G->arcs[l][j]==1 && ! visited[j]){
                visited[j] = TRUE;
                visited_sequence[m]=G->vexs[j];
                t[m]=G->vexs[j];
                m++;
            }else{
                if(G->arcs[j][l]==1 && ! visited[j]){
                    visited[j] = TRUE;
                    visited_sequence[m]=G->vexs[j];
                    t[m]=G->vexs[j];
                    m++;
                }
            }
        }
    }
    printf("\n");
}

int main () {
  int i;
  MGraph *G;
  Boolean visited[MVNum];

  create_graph(&G,"graph_data.txt"); //建立邻接矩阵

  for(i=0; i<MVNum; i++) {
    visited[i] = FALSE;
  }
  char dfs_sequence[MVNum] = {'\0'};
  int visited_order = 0;
  dfs(G, 0, visited, dfs_sequence, &visited_order); //深度优先遍历。 应该输出：abdhecfg
  printf("Print Graph DFS: ");
  printf("%s\n", dfs_sequence);
  printf("\n");

  for(i=0; i<MVNum; i++) {
    visited[i] = FALSE;
  }
  char bfs_sequence[MVNum] = {'\0'};
  bfs(G, 0, visited, bfs_sequence); //以序号为3的顶点开始广度优先遍历。应该输出：abcdefgh
  printf("Print Graph BFS: ");
  printf("%s\n", bfs_sequence);
  printf("True Graph BFS:abcdefgh");
  printf("\n");

  for(i=0; i<MVNum; i++) {
    visited[i] = FALSE;
  }
  char bfs_sequence2[MVNum] = {'\0'};
  bfs(G, 3, visited, bfs_sequence2); //以序号为3的顶点开始广度优先遍历。应该输出：dbhaecfg
  printf("Print Graph BFS: ");
  printf("%s\n", bfs_sequence2);
  printf("True Graph BFS:dbhaecfg");
  printf("\n");

  return 0;
}